class Solution
{
public:
    long long findKthSmallest(vector<int> &coins, int k)
    {
        int m = coins.size();
        vector<long long> lcms(1 << m, 1);
        for (int i = 0; i < (1 << m); ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (i & (1 << j))
                {
                    lcms[i] = lcm(lcms[i], coins[j]);
                }
            }
        }

        auto check = [&](long long target)
        {
            long long cnt = 0;
            for (int i = 1; i < (1 << m); ++i)
            {
                if (__builtin_popcount(i) & 1)
                {
                    cnt += target / lcms[i];
                }
                else
                {
                    cnt -= target / lcms[i];
                }
            }
            return cnt >= k;
        };

        long long l = 0, r = 1e18;
        while (l < r)
        {
            long long mid = l + (r - l) / 2;
            if (check(mid))
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        return l;
    }
};